package main

import "fmt"

// 定义链表结构体
type ListNode struct {
	Val  int
	Next *ListNode
}

//递归法
// 合并两个有序链表，返回合并后的链表头节点
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2 // list1 为空，则直接返回 list2
	} else if list2 == nil {
		return list1 // list2 为空，则直接返回 list1
	} else if list1.Val < list2.Val {
		//合并 list1.Next 和 list2
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		//合并 list1 和 list2.Next
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}

func main() {
	// 定义两个有序链表 l1 和 l2
	l1 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: nil}}}
	l2 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: nil}}}

	// 调用 mergeTwoLists 函数将 l1 和 l2 合并
	merged := mergeTwoLists(l1, l2)

	// 输出合并后链表
	for p := merged; p != nil; p = p.Next {
		fmt.Printf("%d ", p.Val)
	}
}

